class Solution {
public:
    vector<int> rearrangeBarcodes(vector<int>& barcodes) {
        unordered_map<int, int> hash; // 数和其出现的次数
        int mostVal = 0, maxCount = 0;
        for(auto& e : barcodes) // 统计每个数出现的频次
        {
            ++hash[e];
            if(maxCount < hash[e])
            {
                maxCount = hash[e];
                mostVal = e;
            }
        }
        
        int n = barcodes.size(), index = 0;
        vector<int> ret(n);
        for(int i = 0; i < maxCount; ++i) // 先处理出现次数最多的数
        {
            ret[index] = mostVal;
            index += 2;
        }
 
        hash.erase(mostVal);
        for(auto& [a, b] : hash) // 处理剩下的数
        {
            for(int i = 0; i < b; ++i)
            {
                if(index >= n)
                    index = 1;
                ret[index] = a;
                index += 2;
            }
        }
        return ret;
    }
};